题面

题目描述

上午的训练结束了，THU ACM小组集体去吃午餐，他们一行$N$人来到了著名的十食堂。这里有两个打饭的窗口，每个窗口同一时刻只能给一个人打饭。由于每个人的口味（以及胃口）不同，所以他们要吃的菜各有不同，打饭所要花费的时间是因人而异的。另外每个人吃饭的速度也不尽相同，所以吃饭花费的时间也是可能有所不同的。

THU ACM小组的吃饭计划是这样的：先把所有的人分成两队，并安排好每队中各人的排列顺序，然后一号队伍到一号窗口去排队打饭，二号队伍到二号窗口去排队打饭。每个人打完饭后立刻开始吃，所有人都吃完饭后立刻集合去六教地下室进行下午的训练。

现在给定了每个人的打饭时间和吃饭时间，要求安排一种最佳的分队和排队方案使得所有人都吃完饭的时间尽量早。

假设THU ACM小组在时刻$0$到达十食堂，而且食堂里面没有其他吃饭的同学（只有打饭的师傅）。每个人必须而且只能被分在一个队伍里。两个窗口是并行操作互不影响的，而且每个人打饭的时间是和窗口无关的，打完饭之后立刻就开始吃饭，中间没有延迟。

现在给定$N$个人各自的打饭时间和吃饭时间，要求输出最佳方案下所有人吃完饭的时刻。

输入输出格式

输入格式：

第一行一个整数N，代表总共有$N$个人。

以下$N$行，每行两个整数 $Ai$，$Bi$。依次代表第$i$个人的打饭时间和吃饭时间。

输出格式：

一个整数$T$，代表所有人吃完饭的最早时刻。

输入输出样例

输入样例#1：

5
2 2
7 7
1 3
6 4
8 5

输出样例#1：

17

说明

所有输入数据均为不超过200的正整数。

前言

果然，我还是太菜了

解题思路

贪心+DP

对于如此小的数据范围，果断想到$DP$，但是我并没有想到

其实本题和这道题，有异曲同工之妙，其实纯属瞎掰，不过$author$都做不来是真的

于是从这道题里就可以总结出一点做题的经验，对于要求分成两组的，而且数据范围不大的题目，我们可以果断使用$DP$（当然啦，还要满足$DP$的前提——没有后效性）

首先来证明贪心，先按照第二关键字从大到小排序，也就是按照吃饭的时间$a[i].b$排序

但是为什么呢？

为什么贪心是正确的，感性理解一下

用一个序列表示排队的顺序，

假设$i$和$j$分别为俩个人，

$i<j$ ，$i$ 在 $j$ 的前面，

且 $a[i].b<a[j].b$ ，即 $i$ 吃饭比 $j$ 慢，

设，整个序列由 $i$ 和 $j$ 两个位置决定，又因为 $i$ 耗的时间肯定比 $j$ 少，所以整个序列的时间由 $j$ 决定

则，如果交换 $i$ 和 $j$ 位置，

那么对于原本 $j$ 的位置来说，

等待时间不变，吃饭时间变短，答案变优，

对于原本的 $i$ 的位置说，$j$ 移到 $i$ 位置之后，等待时间变短，吃饭时间不变，因此答案也变优

综上，吃饭时间 $a[i].b$ 较长的人应该放在前面

证毕！！！

没那么夸张，但是真的证明完了 $qwq$

接下去是 $DP$ ，也就是开三维表示一下：

$f[i][j][k]$ ：在 $i$ 这个点，$1$ 号窗的等待时间为 $j$，$2$ 号窗的等待时间为 $k$ 时的答案

三维明显会炸

稍微观察一下：$j+k$ 是不是定值啊，就是等于前 $i$ 个人的等待时间总和，于是我们可以维护一下前缀和 $sum[i]$，然后将数组变成两维的

接下去，转移方程就比较好推了：

当然啦，$j<a[i].a$ 时，有些转移就无效了 否则RE爽死

Code

#include<bits/stdc++.h>
#define rgt register
#define INF 0x7f7f7f7f
#define M 40007
#define N 203
using namespace std;
struct node{
    int a,b;
}a[N];
int n,sum[N],f[N][M],ans=INF;
inline int read() {
    rgt int s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
inline bool cmp(node a,node b) {return a.b>b.b;}
int main()
{
    int i,j;
    n=read();
    for(i=1;i<=n;i++)
        a[i].a=read(),a[i].b=read();
    memset(f,INF,sizeof(f));//全都初始化为INF
    sort(a+1,a+n+1,cmp),f[0][0]=0;//初始状态为啥都没有
    for(i=1;i<=n;i++) sum[i]=sum[i-1]+a[i].a;//处理前缀和
    for(i=1;i<=n;i++) {
        for(j=0;j<a[i].a;j++)
            if(f[i-1][j]!=INF)//一些不可能的状态就不要转移了
                f[i][j]=max(f[i-1][j],sum[i]-j+a[i].b);
        for(j=a[i].a;j<=sum[i];j++) {
            if(f[i-1][j]!=INF)
                f[i][j]=max(f[i-1][j],sum[i]-j+a[i].b);
            if(f[i-1][j-a[i].a]!=INF)
                f[i][j]=min(f[i][j],max(f[i-1][j-a[i].a],j+a[i].b));
        }
    }
    for(i=1;i<=sum[n];i++) ans=min(ans,f[n][i]);
    printf("%d",ans);
    return 0;
}

devil.